package com.linchong.linkedlist.medium;

import java.util.*;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-12-01 8:26
 * @Description: CopyListWithRandomPointer$复制带随机指针的链表-138
 * 给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
 *
 * 要求返回这个链表的 深拷贝。 
 *
 * 我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
 *
 * val：一个表示 Node.val 的整数。
 * random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer
 *
 * 关键：利用两个map分别记录新旧两个链表节点的地址
 *
 * 1.原来的链表任意的的节点的random指针的指向位置
 * 2.新链表任意的节点对应的位置
 *
 * 原链表节点地址->节点位置（第几个节点）
 *
 * 节点位置->新链表节点地址
 *
 */
@SuppressWarnings("unused")
public class CopyListWithRandomPointer {

	class Node {
		int val;
		Node next;
		Node random;

		public Node(int val) {
			this.val = val;
			this.next = null;
			this.random = null;
		}

		@Override
		public boolean equals(Object o) {
			if (this == o) {
				return true;
			}
			if (o == null || getClass() != o.getClass()){
				return false;
			}
			Node node = (Node) o;
			return val == node.val &&
					Objects.equals(next, node.next) &&
					Objects.equals(random, node.random);
		}

		@Override
		public int hashCode() {
			return Objects.hash(val, next, random);
		}
	}

	public Node copyRandomList(Node head) {

		//存储地址的map,地址->位置
		Map<Node,Integer> nodeMap = new LinkedHashMap<>();
		// 新链表的第几号节点是谁，位置->地址
		List<Node>  nodeList=new ArrayList<>();

		Node ptr = head;
		int i = 0;
		while(ptr!=null){
			// 存储新链表，下标位置->元素地址
			nodeList.add(new Node(ptr.val));
			// 存储旧链表，K:地址，Value:位置
			nodeMap.put(ptr,i);
			ptr = ptr.next;
			// 记录节点位置
			i++;
		}
		//最后一个指针执行null
        nodeList.add(null);
		ptr = head;
		i = 0;
		while(ptr!=null){
			nodeList.get(i).next = nodeList.get(i+1);
			if(ptr.random!=null){
				int id = nodeMap.get(ptr.random);
				nodeList.get(i).random = nodeList.get(id);
			}
			ptr = ptr.next;
			i++;
		}
		return nodeList.get(0);
	}
}







